package code.homework;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author cc
 * @create 2023-02-14  22:01
 */
public class FindMinHeightTrees {

    //dfs

    /**
     *
     *
     *  数据结构为 List<List<Integer>> arr  ,arr[i]代表 元素i的邻居列表
     *  当 arr[i].size == 1,该元素为最外层叶子节点
     *  循环减掉最外层叶子节点，直至最终所有元素的邻居个数都为 1，此时该元素本身即为结果之一
     */
    public static List<Integer> findMinHeightTrees(int n, int[][] edges) {
        ArrayList<Integer> res = new ArrayList<>();
        if(n ==1){
            res.add(0);
            return res;
        }

        List<List<Integer>> arr = new ArrayList<>();
        for(int i = 0 ; i < n ; i++ ){
            arr.add(new ArrayList<>());
        }

        for (int[] edge: edges) {
            arr.get(edge[0]).add(edge[1]);
            arr.get(edge[1]).add(edge[0]);
        }

        Deque<Integer> deque = new LinkedList<Integer>();
        for (int i = 0; i < n; i++ ){
            if(arr.get(i).size() == 1){
                deque.add(i);
            }
        }

        while (!deque.isEmpty()) {
            res = new ArrayList<>();
            int size = deque.size();
            for (int i = 0 ; i < size ; i++){
                Integer poll = deque.poll();
                res.add(poll);
                List<Integer> neighbors  = arr.get(poll);
                for (int ele :neighbors) {
                    arr.get(ele).remove(arr.get(ele).indexOf(poll));
                    if(arr.get(ele).size() == 1) {
                        deque.add(ele);
                    }
                }

            }
        }
        return res;
    }


    public static void main(String[] args) {
        int[][] edges = {{1,0},{1,2},{1,3}};
        System.out.println(findMinHeightTrees(4,edges));
    }


}
